package twobranchTree.haspathsum;

import java.util.LinkedList;

import twobranchTree.preorderTraversal.TreeNode;

/**
 * @Date 2020/2/24
 * @author 王光浩
 * @Thinking 使用迭代方法。
 *           复杂度分析：时间复杂度O（n），空间复杂度O（2n）
 */
public class MyMethodTwo {
	public boolean hasPathSum(TreeNode root, int sum) {
		LinkedList<TreeNode> stack=new LinkedList<TreeNode>(); //保存树中的节点
		LinkedList<Integer> number=new LinkedList<Integer>();  //保存从该节点到root节点路径的节点值之和
		if(root!=null) {
			stack.add(root);number.add(root.val);
		}
		while(!stack.isEmpty()) {
			TreeNode node=stack.pollFirst();  //获取第一个节点
			Integer numb=number.pollFirst();  //获取该节点对于的路径和
			if(node.left==null && node.right==null) {  //叶子节点
				if(numb==sum)return true;
			}
			else {  //非叶子节点
				if(node.right!=null) {
					stack.add(node.right);number.add(node.right.val+numb);
				}
				if(node.left!=null) {
					stack.add(node.left);number.add(node.left.val+numb);
				}
			}
		}
		return false;
	}
}
